//头结点
class LinkedNodeHead {
	constructor() {
		this.head = null
	}
}
// 普通节点
class LinkedNode {
	constructor(element) {
		this.element = element
		this.next = null
	}
}
// 单链表
class SingleNodeList {
	constructor() {
		this.head = new LinkedNodeHead() // 初始化头节点
		this.length = 0
	}
	// 向尾部添加一元素
	append(element) {
		const newNode = new LinkedNode(element)
		if (this.length === 0) {
			this.head = newNode
		} else {
			let current = this.head
			while (current.next) {
				current = current.next
			}
			current.next = newNode
		}
		this.length += 1
	}
	// 根据指定位置添加元素 true/false
	insert(position, element) {
		const newNode = new LinkedNode(element)
		if (position > this.length || position < 0) return false

		if (position === 0) {
			newNode.next = this.head
			this.head = newNode
			this.length += 1
			return true
		}

		let cur = this.head
		let pre = null
		let i = 0
		while (i++ < position) {
			pre = cur
			cur = cur.next
		}
		pre.next = newNode
		newNode.next = cur
		this.length += 1
		return true
	}
	// 根据位置获取元素  element
	get(postion) {
		if (postion >= this.length || postion < 0) return null
		let i = 0
		let cur = this.head
		while (i++ < postion) {
			cur = cur.next
		}
		return cur.element
	}
	// 查找元素所在位置 -1 / position
	indexOf(element) {
		let cur = this.head
		if (!this.head.element) return -1
		let i = 0
		while (cur) {
			if (cur.element === element) {
				break
			}
			i++
			cur = cur.next
		}
		return i === this.length ? -1 : i
	}
	// 根据指定位置更新元素 true/false
	update(position, element) {
		if (position >= this.length || position < 0) return false
		let i = 0
		let cur = this.head
		while (i < position) {
			cur = cur.next
			i++
		}
		cur.element = element
		return true
	}
	//根据指定位置移除元素 null/element
	removeAt(position) {
		if (position >= this.length || position < 0) return null
		let cur = this.head
		if (this.length === 1) {
			this.head = null
		} else {
			if (position === 0) {
				this.head = cur.next
			} else {
				let i = 0
				cur = this.head
				let pre = null
				while (i < position) {
					pre = cur
					cur = cur.next
					i++
				}
				pre.next = cur.next
			}
		}

		this.length -= 1
		return cur.element
	}
	// 移除元素  null / element
	remove(element) {
		// let cur = this.head
		// let pre = null
		// let flag = false
		// if (element === this.head.element) {
		// 	const el = this.head.element
		// 	this.head = cur.next
		// 	return el
		// }
		// while (cur) {
		// 	if (cur.element === element) {
		// 		flag = true
		// 		break
		// 	}
		// 	pre = cur
		// 	cur = cur.next
		// }
		// if (flag) {
		// 	pre.next = cur.next
		// 	this.length -= 1
		// 	return cur.element
		// } else {
		// 	return null
		// }
		const position = this.indexOf(element)
		if (position !== -1) {
			return this.removeAt(position)
		} else {
			return null
		}
	}
	// 销毁链表
	destroy() {
		this.head = null
		this.length = 0
	}
	// 空链表
	isEmpty() {
		return this.length === 0
	}
	// 链表大小
	size() {
		return this.length
	}
	// 打印输出
	toString() {
		let currentNode = this.head

		let strList = []
		while (currentNode) {
			strList.push(currentNode.element)
			currentNode = currentNode.next
		}
		return strList.join(' ==> ')
	}
}
